package algorithm.t202110;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/30 10:46
 * @description :5道
 * 人间有味是清欢。
 * persevere to last
 * 2021.10.30
 * 李红磊
 */
public class t20211030 {

    //260.只出现一次的数字||
    static public int[] singleNumber(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == Integer.MAX_VALUE) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                if ((nums[i] ^ nums[j]) == 0) {
                    nums[i] = Integer.MAX_VALUE;
                    nums[j] = Integer.MAX_VALUE;
                    break;
                }

            }


        }

        int num = 0;
        for (int item : nums) {
            if (item != Integer.MAX_VALUE) {
                num++;
            }
        }
        int[] res = new int[num];

        int count = 0;
        for (int i : nums) {
            if (i != Integer.MAX_VALUE && count < num) {
                res[count++] = i;
            }

        }


        return res;

    }

    //117.填充每一个节点的下一个右侧节点指针 ||  BFS
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            Node pre = null;

            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();

                if (i > 0) {
                    pre.next = cur;
                }

                pre = cur;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }

                if (cur.right != null) {
                    queue.offer(cur.right);
                }

            }

        }
        return root;

    }

    //572.另一颗树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (subRoot == null) {
            return true;
        }

        return search(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);

    }

    private boolean search(TreeNode root, TreeNode subRoot) {
        if (subRoot == null && root == null) {
            return true;
        }
        if (subRoot == null || root == null) {
            return false;
        }
        if (subRoot.val != root.val) {
            return false;
        }


        return search(root.left, subRoot.left) && search(root.right, subRoot.right);

    }

    //面试题08.08 有重复字符串的排列组合
    ArrayList<String> res = new ArrayList<>();

    public String[] permutation(String S) {
        boolean[] visit = new boolean[S.length()];


        dfs(S, "", visit);
        HashSet<String> hashSet = new HashSet<>();
        ArrayList<String> res2 = new ArrayList<>();

        for (String item : res) {
            if (hashSet.add(item)) {
                res2.add(item);
            }

        }

        return res2.toArray(new String[0]);
    }

    private void dfs(String s, String cur, boolean[] visit) {
        if (cur.length() == s.length()) {
            res.add(cur);
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if (!visit[i]) {
                visit[i] = true;
                dfs(s, cur + s.charAt(i), visit);
                visit[i] = false;
            }

        }

    }

    public String[] permutation2(String S) {
        if (S.length() == 0 || S == null) return new String[0];

        ArrayList<String> list = new ArrayList<>();
        boolean[] visit = new boolean[S.length()];


        dfs2(sort(S), "", visit, list);
        return list.toArray(new String[0]);

    }
    private String sort(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
    /**
     * @return void
     * @Author LiHongLei
     * @Date 2021/10/30 18:08
     * @param: 目标字符
     * @param: path 路径
     * @param: visit 访问数组
     * @param: list 用于返回的集合
     **/
    private void dfs2(String s, String path, boolean[] visit, ArrayList<String> list) {
        if (path.length() == s.length()) {
            list.add(path);
            return;
        }


        for (int i = 0; i < s.length(); i++) {
            //剪枝。
            if (i > 0 && s.charAt(i) == s.charAt(i - 1) && !visit[i - 1]) {
                continue;
            }

            if (!visit[i]) {
                visit[i] = true;
                dfs2(s, path + s.charAt(i), visit, list);
                visit[i] = false;
            }

        }

    }

    //66.加一
    public int[] plusOne(int[] digits) {

        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) {
                return digits;
            }

        }

        int[] res = new int[digits.length + 1];
        res[0]=1;

        return res;

    }


    public static void main(String[] args) {
        t20211030 t20211030 = new t20211030();

        Arrays.stream(t20211030.plusOne(new int[]{9})).forEach(s -> System.out.println(s));


    }


}
